#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
int uniquePaths(int m, int n)
{
    assert(m);
    assert(n);
    int** step = (int**)malloc(sizeof(int*) * m);
    assert(step);
    for (int i = 0; i < m; i++)
    {
        step[i] = (int*)malloc(sizeof(int) * n);
        assert(step[i]);
        step[i][n - 1] = 1;
    }
    for (int i = 0; i < n; i++)
    {
        step[m - 1][i] = 1;
    }
    for (int i = m - 2; i >= 0; i--)
    {
        for (int j = n - 2; j >= 0; j--)
        {
            step[i][j] = step[i + 1][j] + step[i][j + 1];
        }
    }
    return step[0][0];
}

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize)
{
    if (obstacleGrid[obstacleGridSize - 1][obstacleGridColSize[0] - 1] == 1)
        return 0;
    int m = obstacleGridSize;
    int n = obstacleGridColSize[0];
    assert(m);
    assert(n);
    long** step = (long**)malloc(sizeof(long*) * m);
    assert(step);
    int put = 1;
    for (int i = m - 1; i >= 0; i--)
    {
        step[i] = (long*)malloc(sizeof(long) * n);
        assert(step[i]);
        if (obstacleGrid[i][n - 1] == 1)
            put = 0;
        step[i][n - 1] = put;
    }
    put = 1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (obstacleGrid[m - 1][i] == 1)
            put = 0;
        step[m - 1][i] = put;
    }
    for (int i = m - 2; i >= 0; i--)
    {
        for (int j = n - 2; j >= 0; j--)
        {
            if (obstacleGrid[i][j] == 0)
                step[i][j] = step[i + 1][j] + step[i][j + 1];
            else
                step[i][j] = 0;
        }
    }
    return (int)step[0][0];
}

int main()
{
    int** obstacleGrid = (int**)malloc(sizeof(int*) * 9);
    assert(obstacleGrid);
    for (int i = 0; i < 3; i++)
    {
        obstacleGrid[i] = (int*)malloc(sizeof(int) * 3);
        assert(obstacleGrid[i]);
    }
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            obstacleGrid[i][j] = 0;
        }
    }
    obstacleGrid[1][1] = 1;
    int obstacleGridSize = 3;
    int* obstacleGridColSize = (int*)malloc(sizeof(int) * 3);
    assert(obstacleGridColSize);
    for (int i = 0; i < 3; i++)
    {
        obstacleGridColSize[i] = 3;
    }
    printf("%d\n", uniquePaths(3, 3));
    printf("%d\n", uniquePathsWithObstacles(obstacleGrid, obstacleGridSize, obstacleGridColSize));
    return 0;
}